

function HashTable() {
    const H = 37
    const ENLARGE_FACTOR = 0.75
    const SHRINK_FACTOR = 0.25
    const MINIMUM_LEN = 7
    this.storage = []
    this.length = 0
    this.limit = MINIMUM_LEN
    this.loadFactor = this.length / this.limit


    this.hashFunc = function (str, size) {
        //1.定义hashCode变量
        let hashCode = 0
        //2.霍纳算法
        for (let i = 0; i < str.length; i++) {
            hashCode = hashCode * H + str.charCodeAt(i)
        }
        //3.取余操作
        hashCode = hashCode % size
        return hashCode
    }
    this.put = function (key, value) {
        let index = this.hashFunc(key, this.limit)
        let bucket = this.storage[index]
        if (!bucket) {
            bucket = this.storage[index] = []
        }
        for (var i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                tuple[1] = value
                return
            }
        }
        bucket[i] = [key, value]
        this.length++
        this.loadFactor = this.length / this.limit
        if (this.loadFactor >= ENLARGE_FACTOR) {
            this.enlarge()
        }
    }

    this.get = function (key) {
        let index = this.hashFunc(key, this.limit)
        let bucket = this.storage[index]
        if (!bucket) { return }
        for (var i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                return tuple[1]
            }
        }
    }

    this.remove = function (key) {
        let index = this.hashFunc(key, this.limit)
        let bucket = this.storage[index]
        if (!bucket) { return }
        for (var i = 0; i < bucket.length; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                bucket.splice(i, 1)
                this.length--
                this.loadFactor = this.length / this.limit
                if (this.loadFactor <= SHRINK_FACTOR) {
                    this.shrink()
                }
                return tuple[1]
            }
        }
    }

    this.isEmpty = function () {
        return this.length == 0
    }

    this.size = function () {
        return this.length
    }

    this.rezise = function (newLimit) {
        newLimit = newLimit <= MINIMUM_LEN ? MINIMUM_LEN : newLimit
        let oldStorage = this.storage
        this.storage = []
        this.limit = newLimit
        this.length = 0
        for (let i = 0; i < oldStorage.length; i++) {
            let bucket = oldStorage[i]
            if (!bucket) { continue }
            for (let j = 0; j < bucket.length; j++) {
                let tuple = bucket[j]
                this.put(tuple[0], tuple[1])
            }
        }
    }

    this.isPrime = function (num) {
        let maxNum = parseInt(Math.sqrt(num))
        for (let i = 2; i <= maxNum; i++) {
            if (num % i == 0) {
                return false
            }
        }
        return true
    }

    this.getNearbyPrime = function (num) {
        for (let i = num; ; i++) {
            if (this.isPrime(i)) {
                return i
            }
        }
    }

    this.enlarge = function () {
        let newLimit = this.getNearbyPrime(this.limit * 2 + 1)
        this.rezise(newLimit)
        console.log(`现在limt=${this.limit}`)
    }

    this.shrink = function () {
        if (this.limit <= MINIMUM_LEN) { return }
        let newLimit = this.getNearbyPrime(parseInt(this.limit / 2))
        this.rezise(newLimit)
        console.log(`现在limt=${this.limit}`)
    }
}
let h = new HashTable()
for (var i = 1; i <= 40; i++) {
    console.log(i)
    h.put('i' + i, i)
}
for (var i = 1; i <= 40; i++) {
    console.log(i)
    h.remove('i' + i)
}
